package pers.qianyu.month_202102.date_20210202;

import org.junit.*;

/**
 * 424. 替换后的最长重复字符
 * https://leetcode-cn.com/problems/longest-repeating-character-replacement/
 *
 * @author mizzle rain
 * @date 2021-02-02 10:48
 */
public class CharacterReplacement {
    public int characterReplacement(String s, int k) {
        char[] arr = s.toCharArray();
        int len = arr.length;
        int left = 0, right = 0;
        int[] window = new int[26];
        int max = 0;
        while (right < len) {
            char c1 = arr[right++];
            window[c1 - 'A']++;
            max = Math.max(window[c1 - 'A'], max);
            if (right - left - max > k) {
                window[arr[left++] - 'A']--;
            }
            //System.out.println(s.substring(left, right));
        }
        // 为什么当 right 指针走到最后的时候，就是答案呢？
        // 其实，当 right 指针走到最后的时候，left 和 right 组成的区间并不是答案对应的字符串
        // 但是，left 与 right 组成的区间正是答案的长度，因为每当不满足条件的时候，left 和 right 都同时 +1
        // 所以，left 和 right 的长度就一直保持上一个满足条件的长度
        return right - left;
    }

    @Test
    public void test1() {
        int result = new CharacterReplacement()
                .characterReplacement("AABABBA", 1);
        System.out.println("result = " + result);
    }

    @Test
    public void test2() {
        int result = new CharacterReplacement()
                .characterReplacement("ABAB", 2);
        System.out.println("result = " + result);
    }
}
